/*
filepath: /home/debi/IdeaProjects/LearnRust/Work/basic/src/stdx/hashx/hashx.rs
stdx/hashx.rs
CRITICAL: Hash trait、Hasher、常见哈希集合（HashMap/HashSet）示例。已在 collectionsx 中展示集合用法，此处示例关注自定义哈希。
AUTO_COMMENT: 使用标准库的 Hasher 示例来演示自定义键的哈希实现。

#[allow(dead_code)]
pub fn stdx_examples_hashx() {
    use std::hash::{Hash, Hasher};

    #[derive(Debug)]
    struct Key(u64);

    impl Hash for Key {
        fn hash<H: Hasher>(&self, state: &mut H) {
            self.0.hash(state);
        }
    }

    let k = Key(42);
    let _ = k;
}
*/

// ========== 新增：hashx 全面示例与中文注释 ==========
// 本文件展示：
//  - 如何为自定义类型实现 Hash（并确保与 Eq/PartialEq 保持一致）
//  - 如何计算任意值的散列（fingerprint）
//  - HashMap/HashSet 的常见用法
//  - 自定义简单 Hasher 与 BuildHasher 的示例（仅用于教学，非生产用的安全哈希）
//  - DefaultHasher 的随机化说明与可替代方法

use std::collections::{HashMap, HashSet};
use std::hash::Hash as _;
use std::hash::{BuildHasherDefault, Hash, Hasher};
// 明确使用 trait 方法

// ---------------- 计算散列值的辅助函数 ----------------
/// 计算任意可 Hash 值的 64 位散列值（使用 std 的 DefaultHasher）
///
/// 注意：DefaultHasher 在不同进程或不同运行时可能会使用随机种子（为防止哈希攻击），
/// 因此 DefaultHasher 的输出不保证跨进程/跨机器一致。若需要跨进程稳定的哈希，请使用
/// 固定种子的 hasher（如使用 BuildHasherDefault 配合自定义 Hasher），或使用专门的哈希库（例如 sha、xxhash 等）。
pub fn calc_hash_u64<T: Hash + ?Sized>(t: &T) -> u64 {
    // 使用标准库默认的 hasher（实现为一种抵抗哈希冲突攻击的哈希器，细节随实现变化）
    let mut hasher = std::collections::hash_map::DefaultHasher::new();
    t.hash(&mut hasher);
    hasher.finish()
}

// ---------------- 自定义简单 Hasher（教学用，不安全） ----------------
/// 一个非常简单且确定性的 Hasher 实现，仅用于教学。
/// 关键注释：这个 Hasher 不是加密哈希，不能用于安全目的。它简单地采用 XOR 与旋转合并字节。
#[derive(Default, Debug, Clone)]
pub struct SimpleHasher {
    state: u64,
}

impl SimpleHasher {
    pub fn new() -> Self {
        SimpleHasher {
            state: 0xcbf29ce484222325,
        } // 任意初值
    }
}

impl Hasher for SimpleHasher {
    fn finish(&self) -> u64 {
        self.state
    }

    fn write(&mut self, bytes: &[u8]) {
        // 关键注释：演示如何从原始字节累积哈希值；实际生产中请使用成熟的哈希算法
        for &b in bytes {
            // 旋转并异或，是一种非常简单的混合方法
            self.state = self.state.wrapping_mul(0x100_0000_01b3).rotate_left(5) ^ (b as u64);
        }
    }

    // 可选择实现 write_u64/write_u32 等以提高性能，但 write 的默认实现已足够示例
}

// 方便构建 HashMap/HashSet 时使用 BuildHasherDefault
pub type BuildSimpleHasher = BuildHasherDefault<SimpleHasher>;

// ---------------- 自定义 Key 类型示例（Hash + Eq） ----------------
/// 示例结构：CustomKey 包含 id 与 name，但我们只使用 id 作为键的哈希/比较依据（示例场景）
#[derive(Debug, Clone)]
pub struct CustomKey {
    pub id: u64,
    pub name: String,
}

// 关键：当实现 Hash 时，必须与 Eq/PartialEq 的实现保持一致
impl PartialEq for CustomKey {
    fn eq(&self, other: &Self) -> bool {
        // 仅根据 id 比较（示例），因此 Hash 也应仅基于 id
        self.id == other.id
    }
}
impl Eq for CustomKey {}

impl Hash for CustomKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // 关键注释：只将 id 参与哈希，确保与 PartialEq 中的比较语义一致
        self.id.hash(state);
    }
}

// ---------------- 示例用例（作为 #[test]） ----------------
#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::hash_map::DefaultHasher;

    #[test]
    fn test_calc_hash_u64() {
        let s = "hello";
        let h1 = calc_hash_u64(&s);
        let h2 = calc_hash_u64(&s);
        // 同一进程内同一运行中调用应一致
        assert_eq!(h1, h2);

        // 打印用于手动观察（测试中允许）
        println!("hash of {:?} = {:016x}", s, h1);
    }

    #[test]
    fn test_simple_hasher_and_build_hasher() {
        // 使用自定义 SimpleHasher 计算散列
        let mut sh = SimpleHasher::new();
        sh.write(b"abc");
        let hv = sh.finish();
        println!("simple hasher finish = {:016x}", hv);

        // 使用 BuildSimpleHasher 创建一个 HashMap，保证进程内确定性（不受 DefaultHasher 随机种子影响）
        let mut map: HashMap<CustomKey, &str, BuildSimpleHasher> =
            HashMap::with_hasher(BuildSimpleHasher::default());
        map.insert(
            CustomKey {
                id: 1,
                name: "Alice".into(),
            },
            "alice@example.com",
        );
        map.insert(
            CustomKey {
                id: 2,
                name: "Bob".into(),
            },
            "bob@example.com",
        );

        // 根据 id 查找（name 不影响键的等价性）
        let lookup = CustomKey {
            id: 1,
            name: "SomeoneElse".into(),
        };
        assert_eq!(map.get(&lookup), Some(&"alice@example.com"));
    }

    #[test]
    fn test_hashset_and_hashmap_basic() {
        // HashSet 与 HashMap 的基本使用
        let mut set: HashSet<u64> = HashSet::new();
        set.insert(10);
        set.insert(20);
        assert!(set.contains(&10));

        let mut m: HashMap<&str, i32> = HashMap::new();
        m.insert("a", 1);
        m.insert("b", 2);
        assert_eq!(m.get("a"), Some(&1));
    }

    #[test]
    fn test_default_hasher_randomization_note() {
        // 展示 DefaultHasher 在不同进程之间可能产生不同的输出
        let v = "data";
        let mut h = DefaultHasher::new();
        v.hash(&mut h);
        let h1 = h.finish();

        // 重新创建一个 DefaultHasher 并计算，应在同一进程中一致
        let mut h2 = DefaultHasher::new();
        v.hash(&mut h2);
        let h2 = h2.finish();
        assert_eq!(h1, h2);

        // 说明：但不同进程或不同运行时（有随机种子）可能得到不同结果
        println!("DefaultHasher hash = {:016x}", h1);
    }

    #[test]
    fn test_hash_as_fingerprint() {
        // 使用 Hash trait 产生一个 u64 指纹用于快速比较/缓存键
        #[derive(Hash)]
        struct S(i32, i32);
        let s = S(1, 2);
        let f = calc_hash_u64(&s);
        // 指纹不是唯一标识（可能冲突），但常用于快速判断或缓存键
        println!("fingerprint = {:016x}", f);
    }

    // ---------------- HashMap/HashSet 的常见用法 ----------------
    #[test]
    fn hashmap_and_hashset_examples() {
        use std::collections::{HashMap, HashSet};
        let mut map = HashMap::new();
        map.insert("a", 1);
        map.insert("b", 2);
        assert_eq!(map.get("a"), Some(&1));
        // HashSet 用法
        let mut set = HashSet::new();
        set.insert("rust");
        set.insert("go");
        assert!(set.contains("rust"));
    }

    // ---------------- 自定义 Hasher 的用法 ----------------
    #[test]
    fn custom_hasher_example() {
        use std::hash::{BuildHasher, Hasher};
        struct SimpleHasher(u64);
        impl Hasher for SimpleHasher {
            fn write(&mut self, bytes: &[u8]) {
                for b in bytes {
                    self.0 = self.0.wrapping_add(*b as u64);
                }
            }
            fn finish(&self) -> u64 {
                self.0
            }
        }
        struct SimpleBuildHasher;
        impl BuildHasher for SimpleBuildHasher {
            type Hasher = SimpleHasher;
            fn build_hasher(&self) -> SimpleHasher {
                SimpleHasher(0)
            }
        }
        use std::collections::HashMap;
        let mut map: HashMap<&str, i32, SimpleBuildHasher> =
            HashMap::with_hasher(SimpleBuildHasher);
        map.insert("hello", 1);
        map.insert("world", 2);
        assert_eq!(map.get("hello"), Some(&1));
    }
}

// ============================================================================
// 第二部分：HashMap 与 HashSet 的高级用法
// ============================================================================

/// HashMap 的高级操作示例
pub fn demo_hashmap_advanced() {
    println!("=== HashMap 高级用法 ===\n");

    use std::collections::HashMap;

    // 1. 使用 entry API 进行高效的插入/更新
    let mut scores: HashMap<String, i32> = HashMap::new();

    // 如果键不存在则插入，存在则不操作
    scores.entry("Alice".to_string()).or_insert(50);
    scores.entry("Bob".to_string()).or_insert(60);

    println!("初始分数: {:?}", scores);

    // 更新已存在的值
    *scores.entry("Alice".to_string()).or_insert(0) += 10;
    println!("Alice 加分后: {:?}", scores.get("Alice"));

    // 2. 使用 or_insert_with 延迟计算默认值
    let mut cache: HashMap<u32, String> = HashMap::new();

    // 只有当键不存在时才会调用闭包
    let value = cache.entry(1).or_insert_with(|| {
        println!("计算昂贵的默认值...");
        "computed_value".to_string()
    });
    println!("获取到的值: {}", value);

    // 3. 使用 and_modify 结合 or_insert
    let mut word_count: HashMap<String, usize> = HashMap::new();
    let text = "hello world hello rust world rust rust";

    for word in text.split_whitespace() {
        word_count
            .entry(word.to_string())
            .and_modify(|count| *count += 1) // 键存在时的操作
            .or_insert(1); // 键不存在时插入 1
    }

    println!("词频统计: {:?}", word_count);

    // 4. 遍历 HashMap
    println!("\n遍历 HashMap:");
    for (key, value) in &word_count {
        println!("  {} => {}", key, value);
    }

    // 5. HashMap 的容量管理
    let mut map = HashMap::with_capacity(100);
    println!("预分配容量: {}", map.capacity());

    // 收缩容量以节省内存
    map.insert("key", "value");
    map.shrink_to_fit();
    println!("收缩后容量: {}", map.capacity());

    // 6. 使用 retain 保留满足条件的元素
    let mut numbers: HashMap<i32, i32> = (0..10).map(|x| (x, x * x)).collect();
    numbers.retain(|&k, _| k % 2 == 0); // 只保留偶数键
    println!("保留偶数键后: {:?}", numbers);
}

/// HashSet 的高级操作示例
pub fn demo_hashset_advanced() {
    println!("\n=== HashSet 高级用法 ===\n");

    use std::collections::HashSet;

    // 1. 集合运算
    let set1: HashSet<i32> = [1, 2, 3, 4, 5].iter().cloned().collect();
    let set2: HashSet<i32> = [4, 5, 6, 7, 8].iter().cloned().collect();

    // 并集
    let union: HashSet<_> = set1.union(&set2).cloned().collect();
    println!("并集: {:?}", union);

    // 交集
    let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
    println!("交集: {:?}", intersection);

    // 差集
    let difference: HashSet<_> = set1.difference(&set2).cloned().collect();
    println!("差集 (set1 - set2): {:?}", difference);

    // 对称差集
    let symmetric_diff: HashSet<_> = set1.symmetric_difference(&set2).cloned().collect();
    println!("对称差集: {:?}", symmetric_diff);

    // 2. 子集和超集判断
    let small: HashSet<i32> = [1, 2].iter().cloned().collect();
    let large: HashSet<i32> = [1, 2, 3, 4].iter().cloned().collect();

    println!("\nsmall 是 large 的子集: {}", small.is_subset(&large));
    println!("large 是 small 的超集: {}", large.is_superset(&small));
    println!("两集合是否不相交: {}", set1.is_disjoint(&set2));

    // 3. 从迭代器创建 HashSet
    let numbers: HashSet<i32> = (0..10).filter(|x| x % 2 == 0).collect();
    println!("\n偶数集合: {:?}", numbers);

    // 4. 使用 drain 移除并迭代所有元素
    let mut set: HashSet<String> = ["a", "b", "c"].iter().map(|s| s.to_string()).collect();

    println!("\n使用 drain 移除元素:");
    for item in set.drain() {
        println!("  移除: {}", item);
    }
    println!("drain 后集合为空: {}", set.is_empty());
}

// ============================================================================
// 第三部分：自定义复杂类型的 Hash 实现
// ============================================================================

/// 复合结构的 Hash 实现示例
#[derive(Debug, Clone)]
pub struct Person {
    pub id: u64,
    pub name: String,
    pub age: u32,
    pub email: String,
}

// 关键注释：我们希望基于 id 和 email 来判断两个 Person 是否相同
impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id && self.email == other.email
    }
}

impl Eq for Person {}

impl Hash for Person {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // 关键注释：Hash 实现必须与 PartialEq 保持一致
        // 如果两个值相等（根据 PartialEq），它们的哈希值必须相同
        self.id.hash(state);
        self.email.hash(state);
    }
}

/// 演示使用自定义 Person 作为 HashMap 的键
pub fn demo_custom_key_in_hashmap() {
    println!("\n=== 自定义类型作为 HashMap 键 ===\n");

    use std::collections::HashMap;

    let mut users: HashMap<Person, String> = HashMap::new();

    let person1 = Person {
        id: 1,
        name: "Alice".to_string(),
        age: 30,
        email: "alice@example.com".to_string(),
    };

    let person2 = Person {
        id: 2,
        name: "Bob".to_string(),
        age: 25,
        email: "bob@example.com".to_string(),
    };

    users.insert(person1.clone(), "Admin".to_string());
    users.insert(person2.clone(), "User".to_string());

    // 查找（创建相同 id 和 email 的 Person）
    let lookup = Person {
        id: 1,
        name: "Different Name".to_string(), // name 和 age 不同
        age: 99,
        email: "alice@example.com".to_string(),
    };

    if let Some(role) = users.get(&lookup) {
        println!("找到用户，角色: {}", role);
    }

    println!("所有用户:");
    for (person, role) in &users {
        println!("  {:?} => {}", person, role);
    }
}

// ============================================================================
// 第四部分：Hash 的性能考虑与常见陷阱
// ============================================================================

/// 演示浮点数作为 HashMap 键的问题
pub fn demo_float_key_issues() {
    println!("\n=== 浮点数作为键的问题 ===\n");

    use std::collections::HashMap;

    // 警告：不要直接使用 f32/f64 作为 HashMap 的键！
    // 原因：NaN != NaN，违反了 Eq 的要求

    // 正确的做法：包装浮点数并实现自定义的 Eq 和 Hash
    #[derive(Debug, Clone, Copy)]
    struct OrderedFloat(f64);

    impl PartialEq for OrderedFloat {
        fn eq(&self, other: &Self) -> bool {
            // 将 NaN 视为相等，或者直接不允许 NaN
            if self.0.is_nan() && other.0.is_nan() {
                true
            } else {
                self.0 == other.0
            }
        }
    }

    impl Eq for OrderedFloat {}

    impl Hash for OrderedFloat {
        fn hash<H: Hasher>(&self, state: &mut H) {
            // 将浮点数转换为字节进行哈希
            // 注意：+0.0 和 -0.0 的位模式不同
            if self.0 == 0.0 {
                // 统一处理 +0.0 和 -0.0
                0_u64.hash(state);
            } else if self.0.is_nan() {
                // 所有 NaN 使用相同的哈希值
                u64::MAX.hash(state);
            } else {
                self.0.to_bits().hash(state);
            }
        }
    }

    let mut map: HashMap<OrderedFloat, String> = HashMap::new();
    map.insert(OrderedFloat(3.14), "Pi".to_string());
    map.insert(OrderedFloat(2.71), "E".to_string());

    println!("浮点数键的 HashMap: {:?}", map);
}

/// 演示 Hash 冲突的影响
pub fn demo_hash_collision_impact() {
    println!("\n=== Hash 冲突的影响 ===\n");

    use std::collections::HashMap;
    use std::time::Instant;

    // 创建一个产生大量冲突的 hasher（仅用于演示）
    #[derive(Default)]
    struct BadHasher {
        state: u64,
    }

    impl Hasher for BadHasher {
        fn finish(&self) -> u64 {
            // 总是返回相同的哈希值，造成最大冲突！
            self.state % 10 // 只有 10 个不同的哈希值
        }

        fn write(&mut self, bytes: &[u8]) {
            for &b in bytes {
                self.state = self.state.wrapping_add(b as u64);
            }
        }
    }

    type BadBuildHasher = BuildHasherDefault<BadHasher>;

    // 使用坏的 hasher
    let start = Instant::now();
    let mut bad_map: HashMap<u64, u64, BadBuildHasher> =
        HashMap::with_hasher(BadBuildHasher::default());
    for i in 0..1000 {
        bad_map.insert(i, i * i);
    }
    let bad_duration = start.elapsed();

    // 使用默认的好 hasher
    let start = Instant::now();
    let mut good_map: HashMap<u64, u64> = HashMap::new();
    for i in 0..1000 {
        good_map.insert(i, i * i);
    }
    let good_duration = start.elapsed();

    println!("坏哈希器插入 1000 个元素耗时: {:?}", bad_duration);
    println!("好哈希器插入 1000 个元素耗时: {:?}", good_duration);
    println!(
        "性能差异: {:.2}x",
        bad_duration.as_nanos() as f64 / good_duration.as_nanos() as f64
    );
}

// ============================================================================
// 第五部分：使用外部哈希库（示例说明）
// ============================================================================

/// 说明如何使用第三方哈希算法
///
/// 常用的哈希库：
/// - `ahash`: 快速且安全的哈希算法，推荐用于 HashMap/HashSet
/// - `seahash`: 简单且快速
/// - `fnv`: 适用于小键的快速哈希
/// - `sha2`, `sha3`: 加密哈希，用于安全目的
/// - `xxhash-rust`: 非常快的非加密哈希
///
/// 使用示例（需要在 Cargo.toml 添加依赖）:
/// ```toml
/// [dependencies]
/// ahash = "0.8"
/// ```
///
/// ```rust
/// use ahash::AHashMap;
///
/// let mut map = AHashMap::new();
/// map.insert("key", "value");
/// ```
pub fn demo_external_hash_libraries() {
    println!("\n=== 外部哈希库说明 ===\n");

    println!("推荐的哈希库：");
    println!("1. ahash - 高性能、DoS 防护好");
    println!("2. fnv - 适用于小整数键");
    println!("3. seahash - 简单快速");
    println!("4. xxhash - 超快速非加密哈希");
    println!("\n在 Cargo.toml 中添加依赖后即可使用");
}

// ============================================================================
// 第六部分：测试与基准
// ============================================================================

#[cfg(test)]
mod advanced_tests {
    use super::*;
    use std::collections::{HashMap, HashSet};

    #[test]
    fn test_hashmap_entry_api() {
        let mut map = HashMap::new();

        // 测试 or_insert
        map.entry("a").or_insert(1);
        assert_eq!(map.get("a"), Some(&1));

        // 测试 and_modify
        map.entry("a").and_modify(|v| *v += 10).or_insert(0);
        assert_eq!(map.get("a"), Some(&11));
    }

    #[test]
    fn test_hashset_operations() {
        let set1: HashSet<_> = [1, 2, 3].iter().cloned().collect();
        let set2: HashSet<_> = [2, 3, 4].iter().cloned().collect();

        // 交集
        let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
        assert_eq!(intersection.len(), 2);
        assert!(intersection.contains(&2) && intersection.contains(&3));

        // 并集
        let union: HashSet<_> = set1.union(&set2).cloned().collect();
        assert_eq!(union.len(), 4);
    }

    #[test]
    fn test_person_as_key() {
        let mut map: HashMap<Person, String> = HashMap::new();

        let p1 = Person {
            id: 1,
            name: "Alice".to_string(),
            age: 30,
            email: "alice@test.com".to_string(),
        };

        map.insert(p1.clone(), "Data".to_string());

        // 相同 id 和 email，但其他字段不同
        let p2 = Person {
            id: 1,
            name: "Different".to_string(),
            age: 99,
            email: "alice@test.com".to_string(),
        };

        assert_eq!(map.get(&p2), Some(&"Data".to_string()));
    }

    #[test]
    fn test_hash_consistency() {
        // 验证相等的值有相同的哈希
        let p1 = Person {
            id: 1,
            name: "A".to_string(),
            age: 20,
            email: "a@test.com".to_string(),
        };

        let p2 = Person {
            id: 1,
            name: "B".to_string(),
            age: 30,
            email: "a@test.com".to_string(),
        };

        // p1 == p2 (根据我们的 PartialEq 实现)
        assert_eq!(p1, p2);

        // 它们的哈希值也必须相同
        let h1 = calc_hash_u64(&p1);
        let h2 = calc_hash_u64(&p2);
        assert_eq!(h1, h2);
    }
}

// ============================================================================
// 主演示函数
// ============================================================================

/// 运行所有 Hash 相关示例
pub fn run_all_hash_examples() {
    println!("╔════════════════════════════════════════════════════════════╗");
    println!("║          Rust std::hash 标准库完整示例                    ║");
    println!("╚════════════════════════════════════════════════════════════╝\n");

    demo_hashmap_advanced();
    demo_hashset_advanced();
    demo_custom_key_in_hashmap();
    demo_float_key_issues();
    demo_hash_collision_impact();
    demo_external_hash_libraries();

    println!("\n=== 重要提示 ===");
    println!("1. Hash 实现必须与 Eq/PartialEq 保持一致");
    println!("2. 不要使用浮点数（f32/f64）直接作为 HashMap 键");
    println!("3. HashMap 的默认 hasher 使用随机种子防止 DoS 攻击");
    println!("4. 使用 entry API 可以避免重复查找，提高性能");
    println!("5. 对于性能敏感的场景，考虑使用 ahash 等第三方库");
    println!("6. 哈希冲突会严重影响性能，选择好的哈希函数很重要");
}
